//给定一个无重复元素的数组 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。 
//
// candidates 中的数字可以无限制重复被选取。 
//
// 说明： 
//
// 
// 所有数字（包括 target）都是正整数。 
// 解集不能包含重复的组合。 
// 
//
// 示例 1： 
//
// 输入：candidates = [2,3,6,7], target = 7,
//所求解集为：
//[
//  [7],
//  [2,2,3]
//]
// 
//
// 示例 2： 
//
// 输入：candidates = [2,3,5], target = 8,
//所求解集为：
//[
//  [2,2,2,2],
//  [2,3,3],
//  [3,5]
//] 
//
// 
//
// 提示： 
//
// 
// 1 <= candidates.length <= 30 
// 1 <= candidates[i] <= 200 
// candidate 中的每个元素都是独一无二的。 
// 1 <= target <= 500 
// 
// Related Topics 数组 回溯算法 
// 👍 1212 👎 0


import java.util.Arrays;
import java.util.List;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    static   public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List<List<Integer>> result = new ArrayList<>();
        if (candidates.length == 0||candidates==null) {
            return result;
        }
        int len=candidates.length;
        int began=0;
        Deque<Integer> path=new ArrayDeque<>();//存储值的列表
        //回溯（使用递归回溯）
        dfs(candidates, target, began,len,result,path);

        return result;
    }
    static void dfs(int[] candidates,int target,int began,int len, List<List<Integer>>result ,Deque<Integer> path){

        if (target==0) {//添加结果 终止搜索

            result.add(new ArrayList<>(path));
            return;
        }

        for (int i=began; i < len; i++) {
            if (target-candidates[i]<0) {//前提数组排好序
                break;
            }
            path.addLast(candidates[i]);//注意path是集合类型
            dfs(candidates, target-candidates[i],i,len,result,path);

            //path是深度搜索树后保留的变量 所以每次结束后要去掉添加的路径 保留公共的路径

            path.removeLast();

        }

    }

}
//leetcode submit region end(Prohibit modification and deletion)
